{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import pandas as pd\n",
    "import holoviews as hv\n",
    "import networkx as nx\n",
    "from holoviews import opts\n",
    "\n",
    "hv.extension('bokeh')\n",
    "\n",
    "defaults = dict(width=400, height=400, padding=0.1)\n",
    "hv.opts.defaults(\n",
    "    opts.EdgePaths(**defaults), opts.Graph(**defaults), opts.Nodes(**defaults))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Visualizing and working with network graphs is a common problem in many different disciplines. HoloViews provides the ability to represent and visualize graphs very simply and easily with facilities for interactively exploring the nodes and edges of the graph, especially using the bokeh plotting interface.\n",
    "\n",
    "The ``Graph`` ``Element`` differs from other elements in HoloViews in that it consists of multiple sub-elements. The data of the ``Graph`` element itself are the abstract edges between the nodes. By default the element will automatically compute concrete ``x`` and ``y`` positions for the nodes and represent them using a ``Nodes`` element, which is stored on the Graph. The abstract edges and concrete node positions are sufficient to render the ``Graph`` by drawing straight-line edges between the nodes. In order to supply explicit edge paths we can also declare ``EdgePaths``, providing explicit coordinates for each edge to follow.\n",
    "\n",
    "To summarize a ``Graph`` consists of three different components:\n",
    "\n",
    "* The ``Graph`` itself holds the abstract edges stored as a table of node indices.\n",
    "* The ``Nodes`` hold the concrete ``x`` and ``y`` positions of each node along with a node ``index``. The ``Nodes`` may also define any number of value dimensions, which can be revealed when hovering over the nodes or to color the nodes by.\n",
    "* The ``EdgePaths`` can optionally be supplied to declare explicit node paths.\n",
    "\n",
    "#### A simple Graph\n",
    "\n",
    "Let's start by declaring a very simple graph connecting one node to all others. If we simply supply the abstract connectivity of the ``Graph``, it will automatically compute a layout for the nodes using the ``layout_nodes`` operation, which defaults to a circular layout:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Declare abstract edges\n",
    "N = 8\n",
    "node_indices = np.arange(N, dtype=np.int32)\n",
    "source = np.zeros(N, dtype=np.int32)\n",
    "target = node_indices\n",
    "\n",
    "\n",
    "simple_graph = hv.Graph(((source, target),))\n",
    "simple_graph"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Accessing the nodes and edges\n",
    "\n",
    "We can easily access the ``Nodes`` and ``EdgePaths`` on the ``Graph`` element using the corresponding properties:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "simple_graph.nodes + simple_graph.edgepaths"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Displaying directed graphs\n",
    "\n",
    "When specifying the graph edges the source and target node are listed in order, if the graph is actually a directed graph this may used to indicate the directionality of the graph. By setting ``directed=True`` as a plot option it is possible to indicate the directionality of each edge using an arrow:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "simple_graph.relabel('Directed Graph').opts(directed=True, node_size=5, arrowhead_length=0.05)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The length of the arrows can be set as an fraction of the overall graph extent using the ``arrowhead_length`` option."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Supplying explicit paths\n",
    "\n",
    "Next we will extend this example by supplying explicit edges:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def bezier(start, end, control, steps=np.linspace(0, 1, 100)):\n",
    "    return (1-steps)**2*start + 2*(1-steps)*steps*control+steps**2*end\n",
    "\n",
    "x, y = simple_graph.nodes.array([0, 1]).T\n",
    "\n",
    "paths = []\n",
    "for node_index in node_indices:\n",
    "    ex, ey = x[node_index], y[node_index]\n",
    "    paths.append(np.column_stack([bezier(x[0], ex, 0), bezier(y[0], ey, 0)]))\n",
    "    \n",
    "bezier_graph = hv.Graph(((source, target), (x, y, node_indices), paths))\n",
    "bezier_graph"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Interactive features"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Hover and selection policies\n",
    "\n",
    "Thanks to Bokeh we can reveal more about the graph by hovering over the nodes and edges. The ``Graph`` element provides an ``inspection_policy`` and a ``selection_policy``, which define whether hovering and selection highlight edges associated with the selected node or nodes associated with the selected edge, these policies can be toggled by setting the policy to ``'nodes'`` (the default) and ``'edges'``."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "bezier_graph.relabel('Edge Inspection').opts(inspection_policy='edges')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In addition to changing the policy we can also change the colors used when hovering and selecting nodes:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "bezier_graph.opts(\n",
    "    opts.Graph(inspection_policy='nodes', tools=['hover', 'box_select'],\n",
    "               edge_hover_line_color='green', node_hover_fill_color='red'))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Additional information\n",
    "\n",
    "We can also associate additional information with the nodes and edges of a graph. By constructing the ``Nodes`` explicitly we can declare additional value dimensions, which are revealed when hovering and/or can be mapped to the color by setting the ``color`` to the dimension name ('Weight'). We can also associate additional information with each edge by supplying a value dimension to the ``Graph`` itself, which we can map to various style options, e.g. by setting the ``edge_color`` and ``edge_line_width``."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "node_labels = ['Output']+['Input']*(N-1)\n",
    "np.random.seed(7)\n",
    "edge_labels = np.random.rand(8)\n",
    "\n",
    "nodes = hv.Nodes((x, y, node_indices, node_labels), vdims='Type')\n",
    "graph = hv.Graph(((source, target, edge_labels), nodes, paths), vdims='Weight')\n",
    "\n",
    "(graph + graph.opts(inspection_policy='edges', clone=True)).opts(\n",
    "    opts.Graph(node_color='Type', edge_color='Weight', cmap='Set1',\n",
    "               edge_cmap='viridis', edge_line_width=hv.dim('Weight')*10))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If you want to supply additional node information without speciying explicit node positions you may pass in a ``Dataset`` object consisting of various value dimensions."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "node_info = hv.Dataset(node_labels, vdims='Label')\n",
    "hv.Graph(((source, target), node_info)).opts(node_color='Label', cmap='Set1')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Working with NetworkX"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "NetworkX is a very useful library when working with network graphs and the Graph Element provides ways of importing a NetworkX Graph directly. Here we will load the Karate Club graph and use the ``circular_layout`` function provided by NetworkX to lay it out:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "G = nx.karate_club_graph()\n",
    "hv.Graph.from_networkx(G, nx.layout.circular_layout).opts(tools=['hover'])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "It is also possible to pass arguments to the NetworkX layout function as keywords to ``hv.Graph.from_networkx``, e.g. we can override the k-value of the Fruchteran Reingold layout"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "hv.Graph.from_networkx(G, nx.layout.fruchterman_reingold_layout, k=1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Finally if we want to layout a Graph after it has already been constructed, the ``layout_nodes`` operation may be used, which also allows applying the ``weight`` argument to graphs which have not been constructed with networkx:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from holoviews.element.graphs import layout_nodes\n",
    "\n",
    "graph = hv.Graph([\n",
    "    ('a', 'b', 3),\n",
    "    ('a', 'c', 0.2),\n",
    "    ('c', 'd', 0.1),\n",
    "    ('c', 'e', 0.7),\n",
    "    ('c', 'f', 5),\n",
    "    ('a', 'd', 0.3)\n",
    "], vdims='weight')\n",
    "\n",
    "layout_nodes(graph, layout=nx.layout.fruchterman_reingold_layout, kwargs={'weight': 'weight'})"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Adding labels"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If the ``Graph`` we have constructed has additional metadata we can easily use those as labels, we simply get a handle on the nodes, cast them to hv.Labels and then overlay them:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "graph = hv.Graph.from_networkx(G, nx.layout.fruchterman_reingold_layout)\n",
    "labels = hv.Labels(graph.nodes, ['x', 'y'], 'club')\n",
    "\n",
    "(graph * labels.opts(text_font_size='8pt', text_color='white', bgcolor='gray'))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Animating graphs"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Like all other elements ``Graph`` can be updated in a ``HoloMap`` or ``DynamicMap``. Here we animate how the Fruchterman-Reingold force-directed algorithm lays out the nodes in real time."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "hv.HoloMap({i: hv.Graph.from_networkx(G, nx.spring_layout, iterations=i, seed=10) for i in range(5, 30, 5)},\n",
    "           kdims='Iterations')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Real world graphs"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As a final example let's look at a slightly larger graph. We will load a dataset of a Facebook network consisting a number of friendship groups identified by their ``'circle'``. We will load the edge and node data using pandas and then color each node by their friendship group using many of the things we learned above."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "kwargs = dict(width=800, height=800, xaxis=None, yaxis=None)\n",
    "opts.defaults(opts.Nodes(**kwargs), opts.Graph(**kwargs))\n",
    "\n",
    "colors = ['#000000']+hv.Cycle('Category20').values\n",
    "edges_df = pd.read_csv('../assets/fb_edges.csv')\n",
    "fb_nodes = hv.Nodes(pd.read_csv('../assets/fb_nodes.csv')).sort()\n",
    "fb_graph = hv.Graph((edges_df, fb_nodes), label='Facebook Circles')\n",
    "\n",
    "fb_graph.opts(cmap=colors, node_size=10, edge_line_width=1,\n",
    "              node_line_color='gray', node_color='circle')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Bundling graphs"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The datashader library provides algorithms for bundling the edges of a graph and HoloViews provides convenient wrappers around the libraries. Note that these operations need ``scikit-image`` which you can install using:\n",
    "\n",
    "```\n",
    "conda install scikit-image\n",
    "```\n",
    "\n",
    "or\n",
    "\n",
    "```\n",
    "pip install scikit-image\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from holoviews.operation.datashader import datashade, bundle_graph\n",
    "bundled = bundle_graph(fb_graph)\n",
    "bundled"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Datashading graphs"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For graphs with a large number of edges we can datashade the paths and display the nodes separately. This loses some of the interactive features but will let you visualize quite large graphs:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "(datashade(bundled, normalization='linear', width=800, height=800) * bundled.nodes).opts(\n",
    "    opts.Nodes(color='circle', size=10, width=1000, cmap=colors, legend_position='right'))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Applying selections"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Alternatively we can select the nodes and edges by an attribute that resides on either. In this case we will select the nodes and edges for a particular circle and then overlay just the selected part of the graph on the datashaded plot. Note that selections on the ``Graph`` itself will select all nodes that connect to one of the selected nodes. In this way a smaller subgraph can be highlighted and the larger graph can be datashaded."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "datashade(bundle_graph(fb_graph), normalization='linear', width=800, height=800) *\\\n",
    "bundled.select(circle='circle15').opts(node_fill_color='white')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To select just nodes that are in 'circle15' set the ``selection_mode='nodes'`` overriding the default of 'edges':"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "bundled.select(circle='circle15', selection_mode='nodes')"
   ]
  }
 ],
 "metadata": {
  "language_info": {
   "name": "python",
   "pygments_lexer": "ipython3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
